package Sudoku;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Sudoku {

    private final int SIZE = 9;  // 数独大小，常量，表示9x9的数独
    private final int SUBGRID_SIZE = 3;  // 子网格大小，常量，表示3x3的子网格
    private final int[][] sudoku;  // 存储数独的二维数组
    private int[][] answer;  // 存储数独解的二维数组

    // 构造函数，初始化数独数组
    public Sudoku() {
        sudoku = new int[SIZE][SIZE];
    }

    // 生成数独游戏
    public void generateSudoku() {
        fillValues(0, 0);  // 填充数独值
        shuffleRowsAndColumns();  // 随机交换数独的行和列
        answer = new int[SIZE][SIZE];
        // 复制数独到答案数组
        for (int i = 0; i < SIZE; i++) {
            System.arraycopy(sudoku[i], 0, answer[i], 0, SIZE);
        }
    }

    // 随机交换数独的行和列
    private void shuffleRowsAndColumns() {
        Random random = new Random();  // 创建随机数生成器对象
        for (int i = 0; i < 3; i++) {  // 以3为单位交换行列，这样交换不会使数独不合法
            int Start = i * SUBGRID_SIZE;  // 计算起始索引
            int End = Start + SUBGRID_SIZE;  // 计算结束索引

            // 随机交换行
            for (int j = Start; j < End; j++) {
                int randomRow = random.nextInt(End - Start) + Start;  // 随机选择范围内的另一行
                swapRows(j, randomRow);  // 调用swapRows方法，交换当前行和随机选择的行
            }

            // 随机交换列
            for (int j = Start; j < End; j++) {
                int randomCol = random.nextInt(End - Start) + Start;  // 随机选择范围内的另一列
                swapCols(j, randomCol);  // 调用swapCols方法，交换当前列和随机选择的列
            }
        }
    }

    // 交换两行的方法
    private void swapRows(int row1, int row2) {
        int[] temp = sudoku[row1];
        sudoku[row1] = sudoku[row2];
        sudoku[row2] = temp;
    }

    // 交换两列的方法
    private void swapCols(int col1, int col2) {
        for (int i = 0; i < SIZE; i++) {
            int temp = sudoku[i][col1];
            sudoku[i][col1] = sudoku[i][col2];
            sudoku[i][col2] = temp;
        }
    }

    // 递归填充数独的方法
    private boolean fillValues(int row, int col) {
        // 如果当前行和列达到数独的最后一个位置，返回true表示数独已经填充完成
        if (row == SIZE - 1 && col == SIZE)
            return true;

        // 如果当前列达到数独的最后一列，换行
        if (col == SIZE) {
            row++;
            col = 0;
        }

        // 如果当前位置已经有数字，跳过当前位置，继续填充下一个位置
        if (sudoku[row][col] != 0)
            return fillValues(row, col + 1);

        // 尝试填充当前位置的数字
        for (int num = 1; num <= SIZE; num++) {
            // 如果当前数字在当前位置是安全的，即不违反数独规则
            if (isSafe(row, col, num)) {
                // 将当前数字填入数独中
                sudoku[row][col] = num;

                // 递归填充下一个位置，如果填充成功，返回true
                if (fillValues(row, col + 1))
                    return true;

                // 如果填充失败，回溯，将当前位置重置为0，尝试其他数字
                sudoku[row][col] = 0;
            }
        }
        // 如果所有数字都尝试过仍然不能满足数独规则，返回false，触发回溯
        return false;
    }

    // 判断在给定位置是否可以放置数字
    private boolean isSafe(int row, int col, int num) {
        return !usedInRow(row, num) && !usedInCol(col, num) && !usedInSubgrid(row - row % SUBGRID_SIZE, col - col % SUBGRID_SIZE, num);
    }

    // 判断某一行是否已经使用了指定数字
    private boolean usedInRow(int row, int num) { //遍历实现
        for (int col = 0; col < SIZE; col++) {
            if (sudoku[row][col] == num)
                return true;
        }
        return false;
    }

    // 判断某一列是否已经使用了指定数字
    private boolean usedInCol(int col, int num) { //遍历实现
        for (int row = 0; row < SIZE; row++) {
            if (sudoku[row][col] == num)
                return true;
        }
        return false;
    }

    // 判断子网格是否已经使用了指定数字
    private boolean usedInSubgrid(int startRow, int startCol, int num) { //遍历实现
        for (int row = 0; row < SUBGRID_SIZE; row++) {
            for (int col = 0; col < SUBGRID_SIZE; col++) {
                if (sudoku[row + startRow][col + startCol] == num)
                    return true;
            }
        }
        return false;
    }

    // 从数独中移除指定数量的数字
    public void removeNumbers(int numToRemove) {
        Random random = new Random();
        for (int i = 0; i < numToRemove; i++) {  // 循环移除指定数量的数字
            int row = random.nextInt(SIZE);  // 随机选择行
            int col = random.nextInt(SIZE);  // 随机选择列

            // 如果已经是空格，重新选择行列，直到找到非空格的位置
            while (sudoku[row][col] == 0) {
                row = random.nextInt(SIZE);
                col = random.nextInt(SIZE);
            }

            int temp = sudoku[row][col];  // 保存要移除的数字
            sudoku[row][col] = 0;  // 移除数字，将相应位置的值设为0
            if (!hasUniqueSolution()) {  // 如果移除数字后数独没有唯一解
                sudoku[row][col] = temp;  // 恢复原始数字
                i--;  // 回退一步，重新尝试移除数字
            }
        }
    }

    // 判断数独是否有唯一解
    private boolean hasUniqueSolution() {
        int[][] copy = new int[SIZE][SIZE];  // 创建数独的副本
        for (int i = 0; i < SIZE; i++) {
            // 复制当前数独的值到副本中
            System.arraycopy(sudoku[i], 0, copy[i], 0, SIZE);
        }
        SudokuSolver solver = new SudokuSolver(copy);  // 创建数独求解器对象，传入副本
        solver.solve();  // 求解数独
        return solver.getCount() == 1;  // 返回数独是否有唯一解
    }

    // 打印当前数独
    public void printArray(int[][] array) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }

    // 玩数独游戏
    public void playGame() {
        Scanner scanner = new Scanner(System.in);
        int score = 0;
        while (true) {
            printArray(sudoku);
            System.out.println("当前分数: " + score);
            System.out.print("请输入要填充数字的行和列以及希望填充的数字（用空格分隔，输入 ans 显示答案并结束游戏）: ");

            String input = scanner.nextLine();
            if (input.equals("ans")) {
                System.out.println("ANS:");
                printArray(answer);
                System.out.println("游戏结束，最终分数: " + score);
                break;
            }
            String[] parts = input.split(" ");
            int row = Integer.parseInt(parts[0].trim()) - 1;
            int col = Integer.parseInt(parts[1].trim()) - 1;
            int num = Integer.parseInt(parts[2].trim());

            if (row >= 0 && row < SIZE && col >= 0 && col < SIZE) {
                if (sudoku[row][col] != 0) {
                    System.out.println("当前格子已有数字，请重新输入。");
                } else if (answer[row][col] == num) {
                    System.out.println("正确！加一分。");
                    score++;
                    sudoku[row][col] = num; // 更新数独
                } else {
                    System.out.println("错误！请重新输入。");
                }
                if (Arrays.deepEquals(sudoku, answer)) {
                    System.out.println("恭喜你已完成了数独！最终分数: " + score);
                    break;
                }
            } else {
                System.out.println("无效的行和列，请重新输入。");
            }
        }
    }
}